1. Field of Invention
The present invention is directed toward the field of warping sets of geometric objects.
2. Description of Related Art
Physical areas are often modeled using geometric objects. Examples of such physical areas include a geographic region and a building""s floor plan. One example of a model using two-dimensional geometric objects is a map of a geographic region, such as a city.
FIG. 1 illustrates a map that is formed by a set of geometric objects. The objects in FIG. 1 include points 60-70, arcs 80-91, and polygons 50-51. Each arc 80-91 represents a road and is bounded at each of its ends by a point. For example, arc 80 is bounded at one end by point 60 and at another end by point 62. Each arc can be co-bounded by one or two polygons. For example, arc 86 is co-bounded by polygons 50 and 51, while arc 85 is only co-bounded by polygon 50. Each polygon 50 and 51 is formed by a set of arcs that define the boundary of the polygon. For example, polygon 50 is defined by boundary arcs 81, 82, 83, 84, 85, and 86.
Different models of the same physical area often provide different quality details about the area. Differences between models of the same area can occur, because models can be distorted, so that all the features in the model are not depicted in their true positions. Such distortions are often localized, with different regions of the model being distorted differently. In paper models, distortion can be caused by paper stretching, folding, and scaling. In electronic models, distortion can be caused when the model is transformed into digital form.
By repositioning different models of the same area, a more accurate new model can be created. FIG. 2 illustrates a map 100 of an area that is neither very smooth nor accurate. FIG. 3 shows a more accurate map 10 of the same area as map 100. The differences between maps 100 and 10 are illustrated in FIG. 4, which shows an overlay of maps 100 and 110. A repositioning process can be performed to utilize the details of both maps 100 and 110 to obtain an improved new map.
The use of repositioning is particularly beneficial and practical is generating electronic maps. There are often many different maps available for a particular region. By making use of a computer to reposition the many maps that are available for a region, a very accurate new map can be generated in a time efficient and cost efficient manner.
One known method for repositioning two models is to warp one model based on the weighted sum of local displacements between points in the two models. In this method, a set of matching points in the models is obtained for selected regions of the models. Displacements between matching points in each selected region are then employed to generate a warping transformation for the selected region. The warping transformation is then used to transform points in one of the models into points in a new model.
However, such a method is inadequate, because it does not provide for maintaining the topology of the original models in the new model. Topology refers to the relative connections and orientations of geometric objects in the model, and its preservation is critical to ensuring the accuracy of the new model. For example, if topology is not preserved, arc intersections which do not exist in either of the original models may be inserted into the new model.
In order to better maintain topology, model-based warping can be employed. One known method of such warping includes the creation of a global transformation model that provides for transforming all of the points in a model into points in a new model. In such a method, all matching points from two existing models are employed to determine parameters for the global transformation model using numerical analysis, such as least mean squares techniques. However, this global approach does not provide for eliminating local distortions, which constitute many of the distortions that are encountered.
Accordingly, there is a need for a warping process that can be applied to models to correct local distortions without compromising topology.
The present invention, roughly described, provides for warping models made from geometric objects, such as electronic maps, to correct local distortions in the models without compromising model topology. The warping is performed by using a set of transformation functions that are derived from relationships between points in a first model that match points in a second model with more accurate positioning. The transformation functions are applied to the points in the first model to generate a new model with reduced distortion.
In order to provide for reducing local distortions, warping is applied to selected corresponding regions of the first model and the second model by triangulating these regions and generating transformation functions for each corresponding pair of triangles. Topology preservation is achieved by identifying matching points in the first model and the second model that have a potential for causing topology deviations. Such matching points are then excluded from the process of developing transformation equations to be used in the warping process.
Matching points with potential for causing topology deviations are identified by triangulating matching points in the selected regions of the first model and the second model and analyzing the resulting triangles. A matching point is identified as having potential for causing topology deviations, if it is a vertex in a triangle in one model that has an inverted corresponding triangle in the other model. A matching point is also identified as having potential for causing topology deviations, if it is a vertex in a triangle having too small an area or height. An iterative process is performed to identify such undesirable matching points.
These and other objects and advantages of the present invention will appear more clearly from the following description in which the preferred embodiment of the present invention has been set forth in conjunction with the drawings.